package 中等.链表;

import util.ListNode;

/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sort-list/?plan=leetcode_75&plan_progress=s9nullg
 */
public class 排序链表_148 {

    public static void main(String[] args) {

        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(6);
        ListNode listNode3 = new ListNode(1);
        ListNode listNode4 = new ListNode(2);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        sortList(listNode1);

    }

    /**
     * 选择排序（超时）
     *
     * @param head
     * @return
     */
    public static ListNode sortList(ListNode head) {
        ListNode curNode = head;

        while (curNode != null) {
            // 需要找到当前节点到最后一个节点的最小节点，和当前节点交换值
            ListNode minNode = curNode.next;

            ListNode minTempNode = minNode;
            while (minTempNode != null) {
                if (minTempNode.val < minNode.val) {
                    minNode = minTempNode;
                }
                minTempNode = minTempNode.next;
            }
            if (minNode != null && minNode.val < curNode.val) {
                replace(minNode, curNode);
            }

            curNode = curNode.next;
        }
        return head;
    }

    private static void replace(ListNode node1, ListNode node2) {
        int val1 = node1.val;
        node1.val = node2.val;
        node2.val = val1;
    }

}
